home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / game / board / Crafty-15.19.lha / crafty-15.19 / src / search.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  21KB  |  489 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6. #include "epdglue.h"
  7.  
  8. /* last modified 06/05/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   Search() is the recursive routine used to implement the alpha/beta         *
  13. *   negamax search (similar to minimax but simpler to code.)  Search() is      *
  14. *   called whenever there is "depth" remaining so that all moves are subject   *
  15. *   to searching, or when the side to move is in check, to make sure that this *
  16. *   side isn't mated.  Search() recursively calls itself until depth is ex-    *
  17. *   hausted, at which time it calls Quiesce() instead.                         *
  18. *                                                                              *
  19. ********************************************************************************
  20. */
  21. int Search(TREE *tree, int alpha, int beta, int wtm, int depth,
  22.            int ply, int do_null) {
  23.   register int moves_searched=0;
  24.   register BITBOARD save_hash_key;
  25.   register int initial_alpha, value=0;
  26.   register int extensions, pieces;
  27.   int threat=0;
  28. /*
  29.  ----------------------------------------------------------
  30. |                                                          |
  31. |   check to see if we have searched enough nodes that it  |
  32. |   is time to peek at how much time has been used, or if  |
  33. |   is time to check for operator keyboard input.  this is |
  34. |   usually enough nodes to force a time/input check about |
  35. |   once per second, except when the target time per move  |
  36. |   is very small, in which case we try to check the time  |
  37. |   at least 10 times during the search.                   |
  38. |                                                          |
  39.  ----------------------------------------------------------
  40. */
  41.   tree->nodes_searched++;
  42.   if (--next_time_check <= 0) {
  43.     next_time_check=nodes_between_time_checks;
  44.     if (CheckInput()) Interrupt(ply);
  45.     time_abort+=TimeCheck(0);
  46.     if (time_abort) {
  47.       abort_search=1;
  48.       return(0);
  49.     }
  50.   }
  51.   if (ply >= MAXPLY-1) return(beta);
  52. /*
  53.  ----------------------------------------------------------
  54. |                                                          |
  55. |   check for draw by repetition.                          |
  56. |                                                          |
  57.  ----------------------------------------------------------
  58. */
  59.   if (RepetitionCheck(tree,ply,wtm)) {
  60.     value=DrawScore(root_wtm==wtm);
  61.     if (value < beta) SavePV(tree,ply,value,0);
  62. #if !defined(FAST)
  63.     if(ply <= trace_level) printf("draw by repetition detected, ply=%d.\n",ply);
  64. #endif
  65.     return(value);
  66.   }
  67. /*
  68.  ----------------------------------------------------------
  69. |                                                          |
  70. |   now call LookUp() to see if this position has been     |
  71. |   searched before.  if so, we may get a real score,      |
  72. |   produce a cutoff, or get nothing more than a good move |
  73. |   to try first.  there are four cases to handle:         |
  74. |                                                          |
  75. |   1. LookUp() returned "EXACT_SCORE" if this score is    |
  76. |   greater than beta, return beta.  otherwise, return the |
  77. |   score.  In either case, no further searching is needed |
  78. |   from this position.  note that lookup verified that    |
  79. |   the table position has sufficient "draft" to meet the  |
  80. |   requirements of the current search depth remaining.    |
  81. |                                                          |
  82. |   2.  LookUp() returned "UPPER_BOUND" which means that   |
  83. |   when this position was searched previously, every move |
  84. |   was "refuted" by one of its descendents.  as a result, |
  85. |   when the search was completed, we returned alpha at    |
  86. |   that point.  we simply return alpha here as well.      |
  87. |                                                          |
  88. |   3.  LookUp() returned "LOWER_BOUND" which means that   |
  89. |   when we encountered this position before, we searched  |
  90. |   one branch (probably) which promptly refuted the move  |
  91. |   at the previous ply.                                   |
  92. |                                                          |
  93. |   4.  LookUp() returned "AVOID_NULL_MOVE" which means    |
  94. |   the hashed score/bound was no good, but it indicated   |
  95. |   that trying a null-move in this position will be a     |
  96. |   waste of time.                                         |
  97. |                                                          |
  98.  ----------------------------------------------------------
  99. */
  100.   switch (LookUp(tree,ply,depth,wtm,&alpha,&beta,&threat)) {
  101.     case EXACT_SCORE:
  102.       if(alpha < beta) SavePV(tree,ply,alpha,1);
  103.       return(alpha);
  104.     case LOWER_BOUND:
  105.       return(beta);
  106.     case UPPER_BOUND:
  107.       return(alpha);
  108.     case AVOID_NULL_MOVE:
  109.       do_null=0;
  110.   }
  111. /*
  112.  ----------------------------------------------------------
  113. |                                                          |
  114. |   now it's time to try a probe into the endgame table-   |
  115. |   base files.  this is done if (a) the previous move was |
  116. |   a capture or promotion, unless we are at very shallow  |
  117. |   plies (<4) in the search; (b) there are less than 5    |
  118. |   pieces left (currently all interesting 4 piece endings |
  119. |   are available.)                                        |
  120. |                                                          |
  121.  ----------------------------------------------------------
  122. */
  123.   if (EGTB_use) {
  124.     if (TotalPieces<=EGTB_use &&
  125.         (TotalPieces<5 || (WhiteRooks && BlackRooks))) do {
  126.       register int wpawn, bpawn;
  127.       int tb_value;
  128.       if (TotalWhitePawns && TotalBlackPawns) {
  129.         wpawn=FirstOne(WhitePawns);
  130.         bpawn=FirstOne(BlackPawns);
  131.         if (FileDistance(wpawn,bpawn) == 1) {
  132.           if(((Rank(wpawn)==RANK2) && (Rank(bpawn)>RANK3)) ||
  133.              ((Rank(bpawn)==RANK7) && (Rank(wpawn)<RANK6)) || 
  134.              EnPassant(ply)) break;
  135.         }
  136.       }
  137.       tree->tb_probes++;
  138. #if defined(SMP)
  139.       Lock(lock_io);
  140. #endif
  141.       if (EGTBScore(tree, ply, wtm, &tb_value)) {
  142. #if defined(SMP)
  143.         UnLock(lock_io);
  144. #endif
  145.         tree->tb_probes_successful++;
  146.         alpha=tb_value;
  147.         if (abs(alpha) > MATE-100) alpha+=(alpha > 0) ? -(ply-1) : +(ply-1);
  148.         else if (alpha == 0) alpha=DrawScore(root_wtm==wtm);
  149.         if(alpha < beta) SavePV(tree,ply,alpha,2);
  150.         return(alpha);
  151.       }
  152. #if defined(SMP)
  153.       UnLock(lock_io);
  154. #endif
  155.     } while(0);
  156.   }
  157. /*
  158.  ----------------------------------------------------------
  159. |                                                          |
  160. |   initialize.                                            |
  161. |                                                          |
  162.  ----------------------------------------------------------
  163. */
  164.   tree->in_check[ply+1]=0;
  165.   tree->extended_reason[ply+1]=no_extension;
  166.   initial_alpha=alpha;
  167.   tree->last[ply]=tree->last[ply-1];
  168. /*
  169.  ----------------------------------------------------------
  170. |                                                          |
  171. |  first, we try a null move to see if we can get a quick  |
  172. |  cutoff with only a little work.  this operates as       |
  173. |  follows.  instead of making a legal move, the side on   |
  174. |  move 'passes' and does nothing.  the resulting position |
  175. |  is searched to a shallower depth than normal (usually   |
  176. |  one ply less but settable by the operator) this should  |
  177. |  result in a cutoff or at least should set the lower     |
  178. |  bound better since anything should be better than not   |
  179. |  doing anything.                                         |
  180. |                                                          |
  181. |  this is skipped for any of the following reasons:       |
  182. |                                                          |
  183. |  1.  the side on move is in check.  the null move        |
  184. |      results in an illegal position.                     |
  185. |  2.  no more than one null move can appear in succession |
  186. |      or else the search will degenerate into nothing.    |
  187. |  3.  the side on move has little material left making    |
  188. |      zugzwang positions more